/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

package Toolkit;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 *
 * @author bambo_000
 */
public class FindPath {
    /* ---Note路线对象--- */
	public class Way {
		String from;
		String to;
		int cost;
	}

	Map map = new HashMap();// 储存所有路线  Store All line
	List reachedWay = new ArrayList();// 储存到达目的地所经过的note   Store all points from start to end
	Map routeMap = new HashMap();// 储存到达目的地所经过的note和所用的时间，key为时间，value为reachedWay

	int shortestTime=0; //储存最短时间，用于只输出最短路径的情况

	/* ---添加路线，双向添加--- */
        /* ---Add Way, bi-directional Add ---*/
	public void addRoute(String note1, String note2, int cost) {
		List noteList1 = (List) map.get(note1);// note1路线集合
		if (noteList1 == null) {
			noteList1 = new ArrayList();
			map.put(note1, noteList1);
		}

		Way way1 = new Way();
		way1.from = note1;
		way1.to = note2;
		way1.cost = cost;

		/* ---不存在该路线，则添加--- */
		if (!noteList1.contains(way1)) {
			noteList1.add(way1);
		}

		List noteList2 = (List) map.get(note2);// note2路线集合
		if (noteList2 == null) {
			noteList2 = new ArrayList();
			map.put(note2, noteList2);
		}
		Way way2 = new Way();
		way2.from = note2;
		way2.to = note1;
		way2.cost = cost;

		/* ---不存在该路线，则添加--- */
		if (!noteList2.contains(way2)) {
			noteList2.add(way2);
		}
	}

	/*---计算最短路径、最短时间---*/
	public void run(String startNote, String endNote) {
		int tempTime = 0;// 储存所花时间的临时变量
		if (reachedWay.contains(startNote)) {// 走过的不走
			return;
		}
                
		reachedWay.add(startNote);// 把经过的note加入到note集合中
		if (reachedWay.size() > 1) {
			/* ---计算所花时间--- */
			List initList = (List) map.get(reachedWay.get(0));

			for (int j = 0; j < initList.size(); j++) {
				Way w = (Way) initList.get(j);
				if (w.to.equals(reachedWay.get(1))) {
					tempTime += w.cost;

			/* ---用于不需要循环输出所有路线，只输出最短路径，效率很高--- */
                                    if(shortestTime!=0&&tempTime>shortestTime){
                                        return;
                                    }
				}
			}

			for (int i = 1; i < reachedWay.size(); i++) {
				// 所经过的note用时加起来
				List toList = (List) map.get(reachedWay.get(i));
				for (int j = 0; j < toList.size(); j++) {
					Way w = (Way) toList.get(j);
					if (i + 1 < reachedWay.size()) {
						if (w.to.equals(reachedWay.get(i + 1))) {
							tempTime += w.cost;

				/* ---用于不需要循环输出所有路线，只输出最短路径，效率很高--- */
                                                    if(shortestTime!=0&&tempTime>shortestTime){
                                                    return;
                                                    }
						}
					}
				}
			}
		}

		/*---到达---*/

		if (startNote.equals(endNote)) {
			 shortestTime=tempTime;
			String route = reachedWay.get(0).toString();
			for (int i = 1; i < reachedWay.size(); i++) {
				route += "->" + reachedWay.get(i).toString();
			}
			//System.out.println(route + "\t用时：" + tempTime);
			routeMap.put(tempTime, route);
			tempTime = 0;
			reachedWay.remove(reachedWay.size() - 1);// 到达后退回去，走下一路线
			return;
		}

		/*---没到达---*/

		// 获得from城市能够到达到城市列表
		List routeList = (List) map.get(startNote);
		for (Iterator iterator = routeList.iterator(); iterator.hasNext();) {
			Way way = (Way) iterator.next();
			run(way.to, endNote);
		}
		reachedWay.remove(reachedWay.size() - 1);// 走完退回去，走下一路线
	}

	/*---输出用时最短的路线---*/
        /*---Display the shortest way---*/
	public void show(String startNote, String endNote) {
		run(startNote, endNote);
		Set s = routeMap.keySet();
		Object[] a = s.toArray();
		int shortestTime = (Integer) a[0];
		for (int i = 0; i < a.length; i++) {
			if ((Integer) a[i] < shortestTime) {
				shortestTime = (Integer) a[i];
			}
		}
		System.out.println("\nThe short time：\n" + routeMap.get(shortestTime) + "\tUsing Time："
				+ shortestTime);
	}

	public static void main(String[] args) {
		FindPath map = new FindPath();
		map.addRoute("J", "A", 10);
		map.addRoute("J", "B", 4);
		map.addRoute("J", "C", 36);
		map.addRoute("A", "D", 3);
		map.addRoute("A", "C", 18);
		map.addRoute("A", "D", 7);
		map.addRoute("E", "A", 3);
		map.addRoute("E", "B", 4);
		map.addRoute("E", "C", 45);
		map.addRoute("E", "D", 16);

		map.show("E", "C");
	}
}
